\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb,graphicx,url,charter}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6.25in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 6.2in { {\bf CS390 Computational Game Theory and Mechanism Design}
     	 \hfill #2 }
       \vspace{4mm}
       \hbox to 6.2in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 6.2in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\handout}[3]{\heading{#1}{#2}{Feng Shi}{}{#3}}

\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\begin{document}
\handout{1}{July 4, 2013}{Problem Set 1}

\paragraph{Problem 1} (No collaborator.) 
\begin{itemize}
\item[(a)] How many (mixed) Nash equilibria does the Rock-Paper-Scissors game have?
Prove your answer.

\textbf{Solution:}

There is no pure Nash equilibrium.\\ There is a unique mixed Nash equilibrium 
$\big((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})\big)$.

\textbf{Proof:}

\begin{itemize}

\item[part 1:] Prove that the strategy profile
$\big((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},\frac{1}{3})\big)$
is a Nash equilibrium.\\
If player $1$ plays the strategy $\delta_1=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$,
then the expectation of utility of player 
$2$ is $$\forall a_2\in A_2 \ , \  E(U_2(a_2,(\frac{1}{3},\frac{1}{3},\frac{1}{3})))
=\frac{1}{3}\cdot 0+\frac{1}{3}\cdot 1+\frac{1}{3}\cdot (-1)=0$$
so the strategy of player $2$ $\delta_2=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ is a best response to
$\delta_1$ and vice versa. So the strategy profile $\big((\frac{1}{3},\frac{1}{3},\frac{1}{3}),
		(\frac{1}{3},\frac{1}{3},\frac{1}{3})\big)$ is a mixed Nash equilibrium.

\item[part 2:] Prove that $\big((\frac{1}{3},\frac{1}{3},\frac{1}{3}),(\frac{1}{3},\frac{1}{3},
	\frac{1}{3})\big)$ is unique.\\
Suppose player $1$ plays a mixed strategy 
$$\delta_1=\big(\delta_1(R),\delta_1(P),\delta_1(S)\big)\neq (\frac{1}{3},\frac{1}{3},\frac{1}{3})$$
Without loss of generality, assume $\delta_1(R)\geq\delta_1(P)$ and $\delta_1(R)\geq\delta_1(S)$, 
then by the assumptions we have $\delta_1(R)>\frac{1}{3}$. Now consider the payoffs of player $2$.
\begin{align*}
E(U_2(\delta_1,P))&=\delta_1(R)\cdot 1+\delta_1(P)\cdot 0+\delta_1(S)\cdot (-1)=\delta_1(R)-\delta_1(S) \\
E(U_2(\delta_1,S))&=\delta_1(R)\cdot (-1)+\delta_1(P)\cdot 1+\delta_1(S)\cdot 0=\delta_1(P)-\delta_1(R)
\end{align*}
And by $\delta_1(S)=1-\delta_1(P)-\delta_1(R)$ we have
$$E(U_2(\delta_1,P))-E(U_2(\delta_1,S))=3\delta_1(R)-1>0$$
So $\delta_2(\delta_2(R),\delta_2(P),0)$ is always a best response to $\delta_1$.

By similar argument we have that $\delta_1(0,\delta_1(P),\delta_1(S))$ is always a best response to 
$\delta_2$.

So by conclusion, a mixed strategy other than $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ is never a
best response to any mixed strategy that is best response to $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$,
so there is no mixed Nash equilibrium other than $\big((\frac{1}{3},\frac{1}{3},\frac{1}{3}),
		(\frac{1}{3},\frac{1}{3},\frac{1}{3})\big)$.
\end{itemize}

By part 1 and part 2 I proved the claim.$\square$

\item[(b)] Find a (mixed) Nash equilibrium of the BoS game other than the pure ones 
shown in class, and prove that it is an equilibrium.

\textbf{Solution:}

A mixed Nash equilibrium is $\big((\frac{2}{2},\frac{1}{3}),(\frac{1}{3},\frac{2}{3})\big)$.

\textbf{Proof:}

Proof left to (c).

\item[(c)] How many equilibria does the BoS game have? Prove your answer.

\textbf{Proof:}

Suppose $(\alpha_1,\alpha_2)$ is a mixed Nash equilibrium. If $\alpha_1=1$ or $\alpha_1=0$
we obtain two pure Nash equilibrium (degenerated). If $0<\alpha_1<1$, by the lemma 
(\cite{OR94}. Lemma 33.2) saying the strategies in the finite support yields same payoff, player
$1$'s action $B$ and $S$ yields same payoff, so $2\alpha_2(B)=\alpha_2(S)$, and 
$\alpha_2(B)=\frac{1}{3}$. Similarly $\alpha_1(B)=\frac{2}{3}$. So there is a unique mixed Nash 
equilibrium $\big((\frac{2}{2},\frac{1}{3}),(\frac{1}{3},\frac{2}{3})\big)$.

\item[(d)] Construct an infinite normal-form game (that is, the players have 
infinitely many strategies) that does not have any (pure or mixed) equilibrium, 
and prove the correctness of your construction.

\textbf{Solution:}

Two players $1$ and $2$ each picks a positive integer, if the both pick the same integer $n$
then $2$ pays $f(n)$ dollars to $a$ with some given utility function $f$ which is positive.\\\\
Given some specific $f$, the game has no Nash equilibrium (mixed or pure).\\
\textbf{Proof:}\\
In equilibrium, all pure responses by player $1$ to player $2$'s mixed strategy ${p_n}$ must yiedls
same expected utility $p_nf(n)$ and vice versa, so a equilibrium 
$$p_n=f(n)^{-1}\big( \sum_{i=1}^{\infty}f(i)^{-1} \big)^{-1}$$
Thus an equilibrium strategy (mixed, and pure strategy is a special case of mixed stratgy) exists
if and only if the series $\displaystyle \sum_{i=1}^{\infty}f(i)^{-1}$ converges. So if $f(n)=n$
for example there is no mixed (or pure) strategy Nash equilibrium.
\end{itemize}

\bigskip

\paragraph{Problem 2} (No collaborator.)

(OR94, Exercises 18.2 and 18.3.) An object is to be assigned to a player in the set $\{1,\dots,n\}$
in exchange for a payment. Player $i$'s valuation of the object is a positive integer $v_i$,
and $v_1>v_2>\cdots > v_n$. The rule to assign the object is a (sealed-bid) auction:
the players simultaneously submit bids (non-negative integers),
and the object is given to the player with the lowest index among those who submit the highest bid,
in exchange for a payment. A player who does not win does not pay.

\begin{itemize}
\item[(a)] In a {\em first price} auction the payment that the winner makes is his own bid. 
A player's utility is his valuation minus his payment if he gets the object, and is 0 otherwise.

Formulate a first price auction as a normal-form game and analyze all of its pure Nash equilibria. 
In particular, show that in all equilibria player 1 obtains the object.

\item[(b)] In a {\em second price} auction the payment that the winner makes is the highest bid 
among those bids of the players who do not win (so that if only one player submits the hghest bid
then the price paid is the {\em second} highest bid).

Show that in a second price auction the bid $v_i$ of any player $i$ is a {\em weakly dominant}
strategy: player $i$'s utility when he bids $v_i$ is {\em at least as high as} his utility when he
bids any other number, regardless of the strategies of the other players. You should first formalize
weak dominance following our definition of strict dominance.

Show that nevertheless there are (``inefficient") equilibria in which the winner is not player 1.
\end{itemize}

\textbf{Solution:}
\begin{itemize}

\item[(a)]

The set of actions of each player $i$ is the same $A_i=[0,\infty)$ which is the set of possible bids.\\
The utility of player $i$ is $v_i-b_i$ if $b_i$ is equal to the highest bid with no same bid
from lower indexed player, and $0$ otherwise.

The Nash equilibrium $b=(b_1,b_2,..,b_n)$ is:
\begin{itemize}
\item[(i.)]  $b_1\in [v_2,v_1]$ 
\item[(ii.)] $\forall i\neq 1$, $b_i\leq b_1$ 
\end{itemize}

Claim: there is no equilibrium that player $1$ does not obtain the object.\\
Suppose some player $x\neq 1$ bids highest and $b_1<b_x$.\\
If $b_x>v_2$ then player $x$ 's utility will be negative, so he can increase his utility by bidding $0$.\\
If $b_x\leq v_2$ then player $1$ can choose any value other than $b_x$ to win with a positive utility.\\
So there is no equilibrium that player $1$ does not obtain the object.

%Suppose the winning bid is $b^*$, we prove $b^*\in [v_2,v_1]$.\\
%First if $b^*>v_1$, player $1$ can reduce his bid so as to increase his utility.\\
%Second if $b^*<v_2$, player $2$ can make his bid in $(v_2,b^*)$ so as to increase his utility.\\

\item[(b)]

The set of actions of each player $i$ is the same $A_i=[0,\infty)$ which is the set of possible bids.\\
The utility of player $i$ is $v_i-b_j$ with $b_j$ the highest bid of other players
if $b_i$ is equal to the highest bid of all players with no same bid from lower indexed player,
and $0$ otherwise.

Definition of weakly dominated: An action $a_i\in A_i$ of player $i$ in a strategic game 
$G<N,{A_i},{u_i}>$ is weakly dominated if there is a mixed strategy $\alpha_i$ of player $i$ such that
$U_i(a_{-i},\alpha_i)\geq u_i(a_{-i},a_i)$ for all $a_{-i}\in A_{-i}$ and $U_i(a_{-i},\alpha_i)
>u_i(a_{-i},a_i)$ for some $a_{-i}\in A_{-i}$. $U_i(a_{-i},\alpha_i)$ is the utility of player $i$
when he uses mixed strategy $\alpha_i$ while other players' action vector is $a_{-i}$.

For player $i$, bid $b_i=v_i$  is a dominant action.\\
Bidding $v_i$ gurantee utility of $0$. Let $b_i'$ is another bid. 
If $\displaystyle \max_{\substack{j\neq i}}b_j \geq v_i$, then with $b_i'$
player $i$ either lose the object or get non-positive utility. \\
if $\displaystyle \max_{\substack{j\neq i}}b_j<v_i$, player $i$ either loses the object or
wins with price of $\displaystyle \max_{\substack{j\neq i}}b_j$ while with $v_i$ he wins at the same
price.\\
An equilibrium in which player $x$ other than player $1$ wins the object, we have $b_1<v_x$ and 
$b_x>v_1$ and $b_j=0$ for any other player $j$.

\end{itemize}

\bigskip

\paragraph{Problem 3} (No collaborator.)

Consider the following game. Each of 15 students simultaneously announces a number in the set 
$\{1, 2, \dots, 100\}$. A prize of \$1 is split equally between all students whose number is 
closest to 1/3 of the class average.
\begin{itemize}
\item[(a)] 
Provide a sequence $(S^0, S^1, \dots, S^K)$ of iterated elimination of strictly dominated strategies.

%\item[(b)] Show that the game has a unique Nash equilibrium (in pure or mixed strategies).
\end{itemize}

\textbf{Solution:}
\begin{itemize}
\item[(a)]
In the first iteration, all numbers in $[34,100]$ will be eliminated, since they can never be
$\frac{1}{3}$ of the avarage number. By similar reason, the rest of the sequence of elimination will
be (one interval at a time) $[12,33],[4,11],[2,3]$ and what is left is $1$.

%\item[(b)]

\end{itemize}
\bibliographystyle{agsm}

\begin{thebibliography}{99}

\bibitem{OR94}{M. J. Osborne and A. Rubinstein. {\em A course in game theory.} MIT Press, 1994.}

\bibitem{NRTV07}{N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (eds). 
	{\em Algorithmic game theory.} Cambridge University Press, 2007.}

\end{thebibliography}

\end{document}








